#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);		\
	freopen(x".out","w",stdout);
#define pb push_back
#define vec vector<int>

int read(){int x = 0,sgn = 1;char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);return x*sgn;}

const int N = 2e6+10;

int n,c,m,a[N],col[N],nxt[N],tr[N],ans[N];

struct ques{int l,r,id;}q[N];
bool operator < (ques a,ques b){return a.l < b.l;}

void add(int x,int y){for(int i = x;i <= n;i += i & -i) tr[i] += y;}
int query(int x,int y = 0){for(;x;x -= x & -x) y += tr[x];return y;}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,c = in,m = in;
	for(int i = 1;i <= n;i++) a[i] = in;
	for(int i = 1;i <= m;i++) q[i].l = in,q[i].r = in,q[i].id = i;
	sort(q + 1,q + m + 1);
	int l = 1;
	for(int i = 1;i <= c;i++) col[i] = n + 1;
	for(int i = n;i >= 1;i--){
		nxt[i] = col[a[i]]; col[a[i]] = i;
	}
	memset(col,0,sizeof col);
	for(int i = 1;i <= n;i++){
		col[a[i]]++; if(col[a[i]] == 2) add(i,1);
	}
	for(int i = 1;i <= m;i++){
		while(l < q[i].l){
			if(nxt[l] <= n){
				add(nxt[l],-1);
				if(nxt[nxt[l]] <= n) add(nxt[nxt[l]],1);
			}
			l++;
		}
		ans[q[i].id] = query(q[i].r);
	}
	for(int i = 1;i <= m;i++) printf("%d\n",ans[i]);
	return 0;
}
